Propositional and Predicate Logic
Core connectives, implication rearrangements, De Morgan's laws, and quantifier negation from the lesson.
Keyboard Shortcuts
💡 Pro tip: Use keyboard shortcuts for faster studying!
Study Smart Tips for Propositional and Predicate Logic
Master these concepts using proven study techniques that actually work:
Active Recall
Test yourself before flipping each card to strengthen memory retention
Spaced Repetition
Review difficult cards more frequently than easy ones
Multiple Sessions
Break study time into shorter, focused sessions
Explain Aloud
Verbalize answers to reinforce understanding
Questions Covered in This Set
10 cards to master
When is P ⇒ Q false?
In exactly one case: P true and Q false. Otherwise it is true (including vacuously, when P is false).
What is a proposition vs. a predicate?
A proposition is definitely true or false (e.g. 3²+4²=5²). A predicate has free variables (e.g. x²=4) and only becomes a proposition when you plug in a value or quantify.
Which rearrangement of P ⇒ Q is logically equivalent to it?
The contrapositive ¬Q ⇒ ¬P. The converse Q ⇒ P and the inverse ¬P ⇒ ¬Q are NOT equivalent.
Give the contrapositive proof that n² even ⇒ n even.
Prove instead: n odd ⇒ n² odd. If n = 2k+1 then n² = 4k² + 4k + 1, which is odd.
State De Morgan's laws.
¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
Rewrite P ⇒ Q without the arrow, then negate it.
P ⇒ Q ≡ ¬P ∨ Q, so ¬(P ⇒ Q) ≡ P ∧ ¬Q — the negation of an implication is NOT an implication.
How do you negate a quantified statement?
Walk left to right, flip every quantifier (∀↔∃), and negate the final predicate: ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x).
Why must you always state the domain of a quantifier?
Truth depends on it: ∀x (x² ≥ 0) is true over ℝ but false over ℂ (take x = i).
Is mathematical 'or' inclusive or exclusive?
Inclusive: P ∨ Q is true when at least one of P, Q is true, including both.
What does it mean that 'if 1 = 2 then I am the Pope' is true?
It's vacuously true — the hypothesis is false, so the implication makes no claim. This is why a theorem says nothing about objects failing its hypotheses.
